#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
#include<fstream>
#include "../../tools/logger/generateArray.h"

class Solution
{
public:
    //贪心+二分 O(nlgn)
    int myGreed(const vector<int>& arr, int N, int L) {
        //最大覆盖点
        int ret = -1;
        cout << "L:" << L << endl;
        for(int i = 0; i < N; i++) {
            int right = arr[i] + L;
            cout << "right:" << right << endl;
            if(arr[N-1] <= right) {
                //越界 直接统计数目
                cout << "out" << endl;
                ret = max(ret,N-i);
            } else {
                //没越界 二分统计数目 找小于等于right的第一个点的下标
                int l = i-1,r = N;
                cout << "l:" << l << " r:" << r << endl;
                while(l + 1 != r) {
                    // int mid = l + (r - l) >> 1;
                    int mid = (l+r)/2;
                    cout << "mid:" << mid << endl;
                    if(arr[mid] <= right) {
                        l = mid;
                    } else {
                        r = mid;
                    }
                }
                cout << "\tl:" << l << endl;
                ret = max(ret,l-i+1);
            }
            cout << "i=" << i << " ret=" << ret << endl;
            cout << endl;
        }
        return ret;
    }
    //精简版本贪心 //arr:节点数组 N:数组长度 L:绳子长度
    int myGreed1(const vector<int>& arr, int N, int L) {
        //最大覆盖点
        int ret = -1;
        for(int i = 0; i < N; i++) {
            int right = arr[i] + L;
            if(arr[N-1] <= right) {
                //越界 直接统计数目
                ret = max(ret,N-i);
            } else {
                //没越界 二分统计数目 找小于等于right的第一个点的下标
                int l = i-1,r = N;
                while(l + 1 != r) {
                    // int mid = l + (r - l) >> 1;
                    int mid = (l+r)/2;
                    if(arr[mid] <= right) {
                        l = mid;
                    } else {
                        r = mid;
                    }
                }
                ret = max(ret,l-i+1);
            }
        }
        return ret;
    }

    //滑动窗口
    int slideWindow(const vector<int>& arr, int N, int L) {
        int left = 0,right = 0;
        int ret = 0;
        while(left < N) {
            //在当前left情况尽可能扩展right
            while(right < N && arr[right] - arr[left] <= L) {
                right++;
            }
            //此时left -- right距离刚好大于绳子 覆盖点 left ~ right-1
            ret = max(ret,right - left);
            left++;
        }
        return ret;
    }

    //AC代码
    int rope(const vector<int>& arr, int N, int L) {
        int l = 0,
            r = 0,
            n = N,
            maxnum = 0;
        while (l < n) {
            while (r < n && arr[r] - arr[l] <= L) r++;
            maxnum = max(maxnum, r - l++);
        }
        return maxnum;
    }


    //对数器
    void test() {
        int testTimer = 1000;
        int minNum = 0;
        int maxNum = 1000;
        for(int i = 0; i < testTimer; i++) {
            int N = rand() % 999;
            vector<int> arr = Garray().generateVector(minNum,maxNum,N);
            set<int> s(arr.begin(),arr.end());
            arr.assign(s.begin(),s.end());
            int L = rand() % 999;
            N = arr.size();
            int ret1 = myGreed1(arr,N,L);
            int ret2 = slideWindow(arr,N,L);
            int ret3 = rope(arr,N,L);
            if(ret1 != ret2) {
                cout << i << endl;
                cout << "arr 数组:" << endl;
                for(auto ait = arr.begin(); ait != arr.end(); ait++) {
                    cout << *ait << " ";
                }
                cout << endl;
                cout << "N:" << N << " L:" << L << endl;
                cout << "ret1:" << ret1 << endl;
                cout << "ret2:" << ret2 << endl;
                cout << "ret3:" << ret3 << endl;
                cout << "oppos" << endl;
                exit(-1);
            }
        }
    }

};


ifstream in("in.txt");
int main() {
    // int N,L;
    // vector<int> arr;
    // in >> N >> L;
    // for(int i = 0; i < N; i++) {
    //     int tem;
    //     in >> tem;
    //     arr.push_back(tem);
    // }
    // int ret = Solution().myGreed1(arr,N,L);
    // int ret = Solution().slideWindow(arr,N,L);
    // cout << "ret:" << ret << endl;
    Solution().test();
    return 0;
}